package interview.hw_od;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 2023.05-B卷-华为OD机试 - 寻找最大价值的矿堆 https://codefun2000.com/p/P1357
 */
public class MaxMineralValue {

    /**
     * 思路：dfs找连通块
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<List<Integer>> numList = new ArrayList<>();
        while (sc.hasNext()) {
            String str = sc.next();
            List<Integer> list = new ArrayList<>();
            for (int i = 0;i < str.length();i++)
                list.add(Integer.parseInt(str.charAt(i)+""));
            numList.add(list);
        }
        boolean[][] used = new boolean[numList.size()][numList.get(0).size()];
        int maxValue = 0;
        for (int i = 0;i < numList.size();i++) {
            for (int j = 0;j < numList.get(0).size();j++) {
                if (!used[i][j]) {
                    maxValue = Math.max(maxValue, dfs(numList, used, i, j));
                }
            }
        }
        System.out.println(maxValue);
    }

    /**
     * 递归：当前格所在矿堆价值等于当前格价值加上上下左右的价值，当超出边界 或遇到已探索过 或者为0的格子时终止
     */
    static int dfs(List<List<Integer>> numList, boolean[][] used, int i, int j) {
        if (i < 0 || i >= numList.size() || j < 0 || j >= numList.get(0).size()
                || used[i][j] || numList.get(i).get(j) == 0) return 0;
        used[i][j] = true;
        int left = dfs(numList, used, i, j-1);
        int right = dfs(numList, used, i, j+1);
        int up = dfs(numList, used, i-1, j);
        int down = dfs(numList, used, i+1, j);
        return left + right + up + down + numList.get(i).get(j);
    }
}
